﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace SAI.nQueens
{
    public class NQueensProblem
    {
        private Node _start;
        private QueenNode _goal;
        private List<Node> _goals;
        private int _size;
        private int count = 1;

        public Node Start { get { return _start; } }
        public Node Goal { get { return _goal; } }

        public NQueensProblem(int size)
        {
            _size = size;
            _goals = new List<Node>();
            _start = initStart();
            initProblem();
            
            //setChildren(_start);
        }

        private void initProblem()
        {
            List<Node> children = _start.OutNeighbors;
            foreach (Node child in children)
            {
                setChildren(child);
            }
        }

        private void setChildren(Node node)
        {
            if (((QueenNode)node).Column == _size - 1)
                return;
            
            int column = ((QueenNode)node).Column + 1;

            for (int i = _size-1; i >= 0; i--)
            {
                QueenNode parent = (QueenNode)node;
                while (parent != null)
                {
                    if (parent.isAttacking(i, column))
                        break;

                    parent = (QueenNode)parent.Parent;    
                }
                if (parent == null)
                {
                    count++;
                    QueenNode q = new QueenNode(i.ToString() + column.ToString());
                    q.Row = i;
                    q.Column = column;
                    q.Parent = node;
                    ((QueenNode)node).OutNeighbors.Add(q);
                    if (column == _size-1)
                    {
                        _goal = q;
                        _goals.Add(q);
                    }
                }
            }
            foreach (Node child in node.OutNeighbors)
            {
                setChildren(child);
            }
        }

        private QueenNode initStart()
        {
            QueenNode start = new QueenNode("start");
            for (int i = 0; i < _size; i++)
            {
                QueenNode q = new QueenNode(i+"0");
                q.Row = i;
                q.Column = 0;
                start.OutNeighbors.Add(q);
            }
            return start;
        }
        public void printSolution(System.IO.StreamWriter file)
        {
            int[,] sol = new int[_size, _size];
            QueenNode parent = _goal;
            while (_goal.Parent != null && parent.Row != -1)
            {
                sol[parent.Row, parent.Column] = 1;
                parent = (QueenNode)parent.Parent;
            }
            for (int i = 0; i < _size; i++)
            {
                for (int j = 0; j < _size; j++)
                {
                    if (sol[i, j] == 1)
                        file.Write(" Q");
                    else
                        file.Write(" -");
                }
                file.WriteLine();
            }
        }
        public void printSolution()
        {
            int[,] sol = new int[_size, _size];
            QueenNode parent = _goal;
            while (_goal.Parent != null && parent.Row != -1)
            {
                sol[parent.Row, parent.Column] = 1;
                parent = (QueenNode)parent.Parent;
            }
            for (int i = 0; i < _size; i++)
            {
                for (int j = 0; j < _size; j++)
                {
                    if(sol[i,j] == 1)
                        Console.Write(" Q");
                    else
                        Console.Write(" -");
                }
                Console.WriteLine();
            }
        }
    }
}
